/*
33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个关键点上旋转。

（即 0 1 2 4 5 6 7 将变成 4 5 6 7 0 1 2）。

给你一个目标值来搜索，如果数组中存在这个数则返回它的索引，否则返回 -1。

你可以假设数组中不存在重复。
*/

/*
1:找到最小的值在什么位置
2:分区间查找target
*/
class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        if(nums.size() == 0) return -1;
        if(nums[0] == target) return 0;
        int high = nums.size() - 1;
        int low = 0;
        int n = high / 2;
        int base = nums[0];
        if(nums[0] > nums[nums.size() - 1]) {
            while(low <= high) {
                if(nums[n] >= base) {
                    low = n + 1;
                } else {
                    high = n - 1;
                }
                n = low + (high - low) / 2;
            }
        }
        if(target > nums[0]) {
            high = low == 0 ? nums.size() - 1 : low - 1;
            low = 0;
        } else {
            high = nums.size() - 1;
        }
        while(low <= high) {
            n = low + (high - low) / 2;
            if(nums[n] > target) {
                high = n - 1;
            } else if(nums[n] == target) {
                return n;
            } else {
                low = n + 1;
            }
        }
        return -1;
    }
};